Package edu.claflin.finder.algo.clustering

Class GirvanNewman

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.clustering.ClusteringAlgorithm

edu.claflin.finder.algo.clustering.GirvanNewman

All Implemented Interfaces:

Processable<Graph,Graph>

public class GirvanNewman
extends ClusteringAlgorithm

Girvan-Newman Algorithm for Community Detection. Based on python's igraph library and JUNG's graph library.

Author:

Cesar Martin

See Also:

• Wikipedia Summary
• Original Paper
• Original igraph implementation
• Original JUNG implementation

Nested Class Summary

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, PROP_PROGRESS

Constructor Summary

Constructors

Constructor	Description
GirvanNewman(ArgumentsBundle args)

Method Summary

Modifier and Type	Method	Description
private Set<Set<Node>>	getComponents(List<Node> nList)	Extracts the weak components from a graph.
ArrayList<Graph>	process(Graph graph)	Performs Edge Betweenness community detection with Girvan-Newman algorithm a given Graph, returning the clustering with the maximum modularity.
String	toString()

Methods inherited from class edu.claflin.finder.algo.clustering.ClusteringAlgorithm

buildCommunityGraphs, isWeighted

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getMinNodeCount, getPartiteNumber, getWeightName, removePropertyChangeListener, setGraphSortOrder, setMinNodeCount, setPartiteNumber, setProgress, setWeightName, zeropad

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Details

GirvanNewman

public GirvanNewman(ArgumentsBundle args)

Method Details

toString

public String toString()

Overrides:

toString in class Object

process

public ArrayList<Graph> process(Graph graph)

Performs Edge Betweenness community detection with Girvan-Newman algorithm a given Graph, returning the clustering with the maximum modularity.

Parameters:

graph - the Graph to perform FastGreedy on

Returns:

the list of Graphs representing the clustering with the maximum modularity

getComponents

private Set<Set<Node>> getComponents(List<Node> nList)

Extracts the weak components from a graph.

Parameters:

nList - the list of Nodes of the Graph

Returns:

the list of weak components